﻿// 0813train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

/*
 给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。

示例 1：
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
 */
int solve01(vector<int>& people, int limit)
{
	//1排序2left=0,right=vec_size-1
	//left+right<=limit result++;left++;right--;
	//left+right>limit right--
	sort(people.begin(), people.end());
	int vec_size = people.size();
	int left = 0;
	int right = vec_size - 1;
	int result = 0;
	while (left<=right)
	{
		if (left==right)
		{
			result += 1;
			break;
		}
		if (people[left]+people[right]<=limit)
		{
			result += 1;
			left++;
			right--;
		}
		else
		{
			result += 1;
			right--;
		}
	}
	return result;

	//solve01
}

/*
 每个月最多有 2 个需求开发，并且每个月需要完成的需求不能超过部门人力。
 请帮部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少？

 输入描述
输入第一行为 M ，第二行为 requirements 。
M 表示需要开发时间要求，requirements 表示每个需求工作量大小
N 为 requirements 长度，1 ≤ N / 2 ≤ M ≤ N ≤ 10000，1 ≤ requirements[i]≤ 10^9
输出描述
对于每一组测试数据，输出部门需要人力需求，行末无多余的空格。

示例1
输入
3
3 5 3 4
输出
6
输入数据两行，第一行输入数据 3 表示开发时间要求，第二行输入数据表示需求工作量大小，输出数据一行，表示部门人力需求。
当选择人力为6时，2个需求量为3的工作可以在1个月里完成，其他2个工作各需要1个月完成。可以在3个月内完成所有需求。
当选择人力为5时，4个工作各需要1个月完成，一共需要4个月才能完成所有需求。
因此6是部门最小的人力需求。
 */

int CalculateTime(vector<int>&oh_vec, int limit)
{
	//int left=0, right=vec_size-1
	//oh_vec[left]+oh_vec[right]<=limit result+=1;left++;right--;
	int vec_size = oh_vec.size();
	int left = 0, right = vec_size - 1;
	int result = 0;
	while (left<=right)
	{
		if (left==right)
		{
			result += 1;
			break;
		}
		if (oh_vec[left]+oh_vec[right]<=limit)
		{
			result += 1;
			left++;
			right--;
		}
		else
		{
			result += 1;
			right--;
		}
	}

	return result;
	//CalculateTime
}

void solve02(vector<int>&oh_vec, int time_limit)
{
	//1排序 2left=[vec_size-1],right=oh_vec[vec_size-1]+oh_vec[vec_size-2]
	sort(oh_vec.begin(), oh_vec.end());

	int vec_size = oh_vec.size();

	//每个月需要完成的需求不能超过部门人力
	//所以left必须left>=max(oh_vec)
	int left = oh_vec[vec_size - 1], right = oh_vec[vec_size - 1] + oh_vec[vec_size - 2] + 1;

	int result = INT_MAX;
	while (left<right)
	{
		int mid = left + (right - left) / 2;
		if (CalculateTime(oh_vec,mid)<=time_limit)
		{
			result = min(result, mid);
			//满足要求，人力调小
			right = mid;
		}
		else
		{
			//完成不了，人力调大
			left = mid + 1;
		}
	}

	cout << result;
	//solve02------
}

/*
 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
 输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
 */
void DFS(vector<vector<char>>& grid, vector<vector<int>>&checked_grid, int r, int c)
{
	//标记访问
	checked_grid[r][c] = true;
	int row_size = grid.size(), column_size = grid[0].size();
	vector<vector<int>>Direction = { {-1,0},{1,0},{0,-1},{0,1} };

	//1不越界2checkedGrid[r][c] == false3grid[r][c] == '1'
	for (auto&dir:Direction)
	{
		int curr_r = r + dir[0];
		int curr_c = c + dir[1];

		bool if_r = curr_r >= 0 && curr_r <= row_size - 1;
		bool if_c = curr_c >= 0 && curr_c <= column_size - 1;

		if (if_r && if_c)
		{
			bool if_visited = checked_grid[curr_r][curr_c];
			bool if_avaiable = grid[curr_r][curr_c] == '1';
			if (!if_visited&&if_avaiable)
			{
				DFS(grid, checked_grid, curr_r, curr_c);
			}
			
		}
	}

	//DFS------
}

int numIslands(vector<vector<char>>& grid) {
	//1记录row_size,column_size
	//2初始化checkedGrid
	//3双重循环
	//4DFS 三个边界条件判断：1不越界2checkedGrid[r][c]==false3grid[r][c]=="1"
	//5跳出DFS,result+=1

	int row_size = grid.size();
	int column_size = grid[0].size();

	vector<int>status_vec(column_size, false);
	vector<vector<int>>checked_grid(row_size, status_vec);

	int result = 0;
	for (int r=0; r<row_size; r++)
	{
		for (int c=0; c<column_size; c++)
		{
			char curr_node = grid[r][c];
			if (curr_node=='1' &&!checked_grid[r][c])
			{
				DFS(grid, checked_grid, r, c);
				result += 1;
			}
		}

	}

	return result;
	//numIslands
}


int main()
{
	{
		//[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
		vector<char>vec_1 = {'1', '1', '1', '1', '0'};
		vector<char>vec_2 = {'1', '1', '0', '1', '0'};
		vector<char>vec_3 = {'1', '1', '0', '0', '0'};
		vector<char>vec_4 = {'0', '0', '0', '0', '0'};
		vector<vector<char>>grid = { vec_1,vec_2,vec_3,vec_4 };
		cout << numIslands(grid);
		return 0;
	}
	{
		/*
		 3
		 3 5 3 4
		 */
		int time_limit;
		cin >> time_limit;
		cin.ignore();

		vector<int>oh_vec;
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		string token;
		while (oh_sstream>>token)
		{
			oh_vec.push_back(stoi(token));
		}

		//vector<int>oh_vec = { 3,5,3,4 };
		//int time_limit = 3;
		solve02(oh_vec, time_limit);

		return 0;
	}
	{
		vector<int>oh_vec = { 3,5,3,4 };
		int limit = 6;
		sort(oh_vec.begin(), oh_vec.end());
		cout << CalculateTime(oh_vec, limit);

		return 0;
	}
	//people = [1,2], limit = 3 1
	//people = [3,2,2,1], limit = 3 3
	vector<int>people = { 3,2,2,1 };
	int limit = 3;
	cout << solve01(people, limit);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
